#include "stdlib.h"

typedef int ElemType;
typedef struct _Node
{
    ElemType data;
    struct _Node *next;
}Node, *LinkList;

/**
 * @brief Get the Length of LinkList
 * 
 * @param l The head of list
 * @param length  The length of list
 */
void getLength(LinkList l, int &length){
    length = 0;
    Node *p = l;
    while(p->next){
        length++;
        p = p->next;
    }
}

/**
 * @brief Get the Elem with the specified list index
 * 
 * @param l list
 * @param i index
 * @param e element 
 * @return state
 */
int getElem(LinkList l, int i, ElemType &e){
    int j = 1;
    Node *p = l->next;
    while(p && j < i){
        j++;
        //继续向后
        p = p->next;
    }
    if(!p){  //i>len of list
        return -1;
    }
    if(j > i){  //i<1
        return -2;
    }

    e = p->data;
    return 0;
}
/**
 * @brief insert element to list
 * 
 * @param l list
 * @param i index
 * @param e element
 */
void insert(LinkList &l, int i, ElemType e){
    Node *p = l->next;
    //计数
    int j = 1;
    while(p && j < i - 1){
        j++;
        p = p->next;
    }
    if(!p || j > i - 1){//非法
        return;
    }
    Node *node = (LinkList) malloc(sizeof(Node));
    node->data = e;
    node->next = p->next;
    p->next = node;
}

/**
 * @brief delete element from list
 * 
 * @param l list
 * @param i index
 * @param e element
 */
void del(LinkList &l, int i, ElemType e){
    Node*p = l;
    int j = 0;
    while(p->next && j < i - 1){
        j++;
        p = p->next;
    }
    if(!p || j > i - 1){
        return;
    }
    Node *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
}

/**
 * @brief Create a linked list whith reverse array element
 * 
 * @param l the head of linked list
 * @param e array
 * @param n the length of array
 */
void createFromTail(LinkList &l, ElemType e[], int n){
    //申请头结点
    l = (LinkList)malloc(sizeof(Node));
    l->next = NULL; //空表
    for(int i = 0; i < n; i++){
        Node *p = (LinkList) malloc(sizeof(Node));
        p->data = e[i];
        //p插入到第一个位置上
        p->next = l->next;
        l->next = p;
    }
}
/**
 * @brief Create a linked list whith array element
 * 
 * @param l the head of linked list
 * @param e array
 * @param n the length of array
 */
void createFromHead(LinkList &l, ElemType e[], int n){
    l = (LinkList)malloc(sizeof(ElemType));
    l->next = NULL;
    Node *tail = l;
    for(int i = 0; i < n; i++){
        Node *p = (LinkList)malloc(sizeof(Node));
        p->data = e[i];
        p->next = NULL;
        //p插入到最后一个位置上
        tail->next = p;
        tail = p;
    }
}

/**
 * @brief print linkedList to console
 * 
 * @param l 
 */
void printLinkedList(LinkList &l){
    LinkList p = l->next;
    while(p){
        printf("%d", p->data);
        if(p->next){
            printf("->");
        }
        p = p->next;
    }
}